"""
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，
因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
"""


def getUglyNumber_solution(index):
    if index == 0:
        return 0
    ugly_number_list = [1]
    i2, i3, i5 = 0, 0, 0
    while len(ugly_number_list) < index:
        n2 = 2 * ugly_number_list[i2]
        n3 = 3 * ugly_number_list[i3]
        n5 = 5 * ugly_number_list[i5]
        min_num = min((n2, n3, n5))
        ugly_number_list.append(min_num)
        if min_num == n2:
            i2 += 1
        if min_num == n3:
            i3 += 1
        if min_num == n5:
            i5 += 1
    return ugly_number_list[index-1]


print(getUglyNumber_solution(8))
